1325E - Ehab's REAL Number Theory Problem - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pi;
#define pb emplace_back
const int MN=78501; 
int N, at=170, a,b, ans = MN; bool pvis[1001]; pi dist[MN];
vector<int> prime, vals, adj[MN]; queue<pi> q; 
unordered_map<int, int> ind; // (value, index it maps to)
void bfs1(int r){ q.push({r,-1}); dist[r]={1,r};
	while(!q.empty()){ pi t = q.front(); int x=t.first, p=t.second; q.pop();
		for(int nx: adj[x]) if(nx!=p && nx>r) { 
			if(dist[nx].second==dist[x].second) ans=min(ans,dist[x].first+dist[nx].first-1);
			else{ dist[nx]={dist[x].first + 1,r}; q.push({nx,x}); } } } }
void bfs(int r){ q.push({r,-1}); dist[r]={1,r};
	while(!q.empty()){ pi t = q.front(); int x=t.first, p=t.second; q.pop();
		for(int nx: adj[x]) if(nx!=p && nx>=r && adj[nx].size()>1) { 
			if(dist[nx].second==dist[x].second) { ans=min(ans,dist[x].first+dist[nx].first-1);
			    if(ans==2) { cout << 2 <<'\n'; exit(0); } }
			else{ dist[nx]={dist[x].first + 1,r}; q.push({nx,x}); } } } }
int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    prime.reserve(170); prime.pb(0); prime.pb(1); 
	for(int i=2;i<=1e3;i++) { if(pvis[i]) continue; prime.pb(i);
		for(int j=i*i;j<=1e3;j+=i) pvis[j]=1; } 
	cin >> N; int x; for (int i=0; i<N; i++) { vals.clear(); cin >> x;
        for (int j=2; j<prime.size() && prime[j] * prime[j] <= x; j++) { int cnt = 0;
            while (x%prime[j] == 0) { x /= prime[j]; cnt++; }
            if (cnt%2 == 1) vals.pb(prime[j]); }
        if (vals.empty() && x == 1) { cout << 1 <<'\n'; return 0; }
        if(x!=1) vals.pb(x);
        for (int k: vals) if (ind.count(k) == 0)  
			{ if (k > 1e3) ind[k] = ++at;				
			  else { int t=lower_bound(prime.begin(),prime.end(),k)-prime.begin();
				     ind[k]=t; } } ind[1]=1;       	
		if(vals.size()==1) adj[1].pb(ind[vals.front()]); 
		else { a=ind[vals.front()]; b=ind[vals.back()]; 
		    if(a==2 || a==3 || a==5) adj[a].pb(b); 
			else adj[a].pb(b); adj[b].pb(a); }         
    } 
    for(int x:{1,2,3,4}) if(adj[x].size()>1) bfs1(x);
	for (int j: prime) if(j>5 && adj[ind[j]].size()>1) bfs(ind[j]);
    cout << (ans == MN ? -1 : ans) <<'\n';
}